package Mycode.BackTrack.Leetcode52.NQueen;

public class Leetcode52 {
 // public int totalNQueens(int n) {
    //     //n 小于 1的化，一个也放不了，直接返回0
    //     if (n < 1) {
    //         return 0;
    //     }
    //     //创建path数组来储存每一行放皇后的列数
    //     //用来判断是否冲突
    //     int[] path = new int[n];

    //     return f1(0, path, n);    
    // }
    public int totalNQueens(int n) {
        if (n < 1) {
            return 0;
        }
        int limit = (1 << n) - 1;
        return f2(limit, 0, 0, 0);
    }

    //位运算的方法   

    private static int f2(int limit, int col, int left, int right) {
        if (col == limit) {
            return 1;
        }
        int ban = col | left | right;
        int ans = 0;
        int Candidate = (~ban) & limit;
        int place = 0;

        while (Candidate != 0) {
            place = Candidate & (-Candidate);
            Candidate ^= place;
            ans += f2(limit, col | place, (left | place) >> 1, (right | place) << 1);
        }
        return ans;
    }

    // 第i行开始搜索， 路径数组， n个皇后
    private static int f1(int i, int[] path, int n) {
        //从第0行开始搜索
        //每一行都进行了合法判断，搜索到了第n行，说明有一种组合合法了
        //返回1
        if (i == n) {
            return 1;
        }
        int ans = 0;
        for (int j = 0; j < n; j++) {
            if (check(i, j, path)) {
                //记住每行使用过的列
                path[i] = j;
                ans += f1(i + 1, path, n);
            }
        }
        return ans;
    }

    private static boolean check(int i, int j,int[] path) {
        for (int k = 0; k < i; k ++) {
            if (j == path[k] || Math.abs(i - k) == Math.abs(j - path[k])) {
                return false;
            }
        }
        return true;
    }
    
}
